home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / pctchnqs / 1991 / number4 / l4.asm < prev    next >
Assembly Source File  |  1991-07-21  |  7KB  |  147 lines
  1. ; Searches a buffer for a specified pattern. In case of a mismatch,
  2. ; uses the value of the mismatched byte to skip across as many
  3. ; potential match locations as possible (partial Boyer-Moore).
  4. ; Returns start offset of first match searching forward, or NULL if
  5. ; no match is found.
  6. ; Requires that the pattern be no longer than 255 bytes, and that
  7. ; there be a match for the pattern somewhere in the buffer (ie., a
  8. ; copy of the pattern should be placed as a sentinel at the end of
  9. ; the buffer if the pattern isn't already known to be in the buffer).
  10. ; Tested with TASM 2.0.
  11. ; C near-callable as:
  12. ;       unsigned char * FindString(unsigned char * BufferPtr,
  13. ;          unsigned int BufferLength, unsigned char * PatternPtr,
  14. ;          unsigned int PatternLength);
  15.  
  16. parms   struc
  17.         dw      2 dup(?) ;pushed BP & return address
  18. BufferPtr dw    ?       ;pointer to buffer to be searched
  19. BufferLength dw ?       ;# of bytes in buffer to be searched
  20.                         ; (not used, actually)
  21. PatternPtr dw   ?       ;pointer to pattern for which to search
  22.                         ; (pattern *MUST* exist in the buffer)
  23. PatternLength dw ?      ;length of pattern for which to search (must
  24.                         ; be <= 255)
  25. parms   ends
  26.  
  27.         .model small
  28.         .code
  29.         public _FindString
  30. _FindString     proc    near
  31.         cld
  32.         push    bp      ;preserve caller's stack frame
  33.         mov     bp,sp   ;point to our stack frame
  34.         push    si      ;preserve caller's register variables
  35.         push    di
  36.         sub     sp,256  ;allocate space for SkipTable
  37. ; Create the table of distances by which to skip ahead on mismatches
  38. ; for every possible byte value. First, initialize all skips to the
  39. ; pattern length; this is the skip distance for bytes that don't
  40. ; appear in the pattern.
  41.         mov     di,ds
  42.         mov     es,di   ;ES=DS=SS
  43.         mov     di,sp   ;point to SkipBuffer
  44.         mov     al,byte ptr [bp+PatternLength]
  45.         and     al,al   ;return an instant match if the pattern is
  46.         jz      InstantMatch ; 0-length
  47.         mov     ah,al
  48.         mov     cx,256/2
  49.         rep     stosw
  50.         mov     ax,[bp+PatternLength]
  51.         dec     ax                       ;from now on, we only need
  52.         mov     [bp+PatternLength],ax    ; PatternLength - 1
  53. ; Point to rightmost byte of first potential pattern match location
  54. ; in buffer.
  55.         add     [bp+BufferPtr],ax
  56. ; Set the skip values for the bytes that do appear in the pattern to
  57. ; the distance from the byte location to the end of the pattern.
  58.         mov     si,[bp+PatternPtr] ;point to start of pattern
  59.         and     ax,ax   ;are there any skips to set?
  60.         jz      SetSkipDone ;no
  61.         mov     di,sp   ;point to SkipBuffer
  62.         sub     bx,bx   ;prepare for word addressing off byte value
  63. SetSkipLoop:
  64.         mov     bl,[si] ;get the next pattern byte
  65.         inc     si      ;advance the pattern pointer
  66.         mov     [di+bx],al ;set the skip value when this byte value is
  67.                         ; the mismatch value in the buffer
  68.         dec     ax
  69.         jnz     SetSkipLoop
  70. SetSkipDone:
  71.         mov     dl,[si] ;DL=rightmost pattern byte from now on
  72.         dec     si      ;point to next-to-rightmost byte of pattern
  73.         mov     [bp+PatternPtr],si ; from now on
  74. ; Search the buffer.
  75.         std                     ;for backward REPZ CMPSB
  76.         mov     di,[bp+BufferPtr] ;point to the first search location
  77.         mov     bx,sp           ;point to SkipTable for XLAT
  78. SearchLoop:
  79.         sub     ah,ah   ;used to convert AL to a word
  80. ; Skip through until there's a match for the first pattern byte.
  81. QuickSearchLoop:
  82. ; See if we have a match at the first buffer location.
  83.         REPT    8       ;unroll loop 8 times to reduce branching
  84.         mov     al,[di] ;next buffer byte
  85.         cmp     dl,al   ;does it match the pattern?
  86.         jz      FullCompare ;yes, so keep going
  87.         xlat            ;no, look up the skip value for this mismatch
  88.         add     di,ax   ;BufferPtr += Skip;
  89.         ENDM
  90.         jmp     QuickSearchLoop
  91. ; Return a pointer to the start of the buffer (for 0-length pattern).
  92.         align   2
  93. InstantMatch:
  94.         mov     ax,[bp+BufferPtr]
  95.         jmp     short Done
  96. ; Compare the pattern and the buffer location, searching from high
  97. ; memory toward low (right to left).
  98.         align   2
  99. FullCompare:
  100.         mov     [bp+BufferPtr],di ;save the current buffer location
  101.         mov     cx,[bp+PatternLength] ;# of bytes yet to compare
  102.         jcxz    Match   ;done if there was only one character
  103.         dec     di      ;point to next dest byte to compare (SI
  104.                         ; points to next-to-rightmost src byte)
  105.         repz    cmpsb   ;compare the rest of the pattern
  106.         jz      Match   ;that's it; we've found a match
  107. ; It's a mismatch; let's see what we can learn from it.
  108.         inc     di      ;compensate for 1-byte overrun of REPZ CMPSB;
  109.                         ; point to mismatch location in buffer
  110. ; # of bytes that did match.
  111.         mov     si,[bp+BufferPtr]
  112.         sub     si,di
  113. ; If, based on the mismatch character, we can't even skip ahead as far
  114. ; as where we started this particular comparison, then just advance by
  115. ; 1 to the next potential match; otherwise, skip ahead from this
  116. ; comparison location by the skip distance for the mismatch character,
  117. ; less the distance covered by the partial match.
  118.         mov     al,[di] ;get the value of the mismatch byte in buffer
  119.         xlat            ;get the skip value for this mismatch
  120.         mov     cx,1    ;assume we'll just advance to the next
  121.                         ; potential match location
  122.         sub     ax,si   ;is the skip far enough to be worth taking?
  123.         jna     MoveAhead ;no, go with the default advance of 1
  124.         mov     cx,ax   ;yes, this is the distance to skip ahead from
  125.                         ; the last potential match location checked
  126. MoveAhead:
  127. ; Skip ahead and perform the next comparison.
  128.         mov     di,[bp+BufferPtr]
  129.         add     di,cx              ;BufferPtr += Skip;
  130.         mov     si,[bp+PatternPtr] ;point to the next-to-rightmost
  131.                                    ; pattern byte
  132.         jmp     SearchLoop
  133. ; Return start of match in buffer (BufferPtr - (PatternLength - 1)).
  134.         align   2
  135. Match:
  136.         mov     ax,[bp+BufferPtr]
  137.         sub     ax,[bp+PatternLength]
  138. Done:
  139.         cld             ;restore default direction flag
  140.         add     sp,256  ;deallocate space for SkipTable
  141.         pop     di      ;restore caller's register variables
  142.         pop     si
  143.         pop     bp      ;restore caller's stack frame
  144.         ret
  145. _FindString     endp
  146.         end
  147.